package linear.linked.doubly;

import java.util.Iterator;

/**
 * 双链表
 * @author caasi
 * @since 2022-01-14 15:47:46
 */
public class DoubleLinkedList<T> implements Iterable<T> {

    //头指针，指向第一个元素
    private Node<T> first;

    //尾指针，指向最后一个元素
    private Node<T> last;

    //链表长度
    private int size;

    public DoubleLinkedList() {
        first = last = null;
        size = 0;
    }

    //清空链表
    public void clear() {
        first = last = null;
        size = 0;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //链表的长度
    public int size() {
        return size;
    }

    //返回下标为i的元素
    public T get(int index) {
        checkIndexSafe(index);
        Node<T> node = node(index);
        return node.value;
    }

    //向链表末尾添加元素
    public void insert(T t) {
        Node<T> l = last;
        Node<T> newNode = new Node<>(l, t, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
    }

    //向链表下标为i的元素之前添加元素
    public void insert(T t, int index) {
        checkIndexSafe(index);
        Node<T> node = node(index);
        Node<T> prev = node.prev;
        Node<T> newNode = new Node<>(prev, t, node);
        if (prev == null)
            first = newNode;
        else
            prev.next = newNode;
        node.prev = newNode;
        size++;
    }

    //删除下标为i的元素并返回
    public T remove(int index) {
        checkIndexSafe(index);
        Node<T> node = node(index);
        Node<T> p = node.prev;
        Node<T> n = node.next;
        if (p == null)
            first = n;
        else
            p.next = n;

        if (n == null)
            last = p;
        else
            n.prev = p;
        size--;
        return node.value;
    }

    //返回链表中首次出现的元素t的下标，如果没有t元素，则返回-1
    public int indexOf(T t) {
        Node<T> node = first;
        int index = 0;
        while (node != null) {
            if (node.value.equals(t))
                return index;
            node = node.next;
            index++;
        }
        return -1;
    }

    //获取链表的第一个元素
    public T getFirst() {
        checkIndexSafe(0);
        return first.value;
    }

    //获取链表的最后一个元素
    public T getLast() {
        checkIndexSafe(size - 1);
        return last.value;
    }

    //查找下标为i的节点
    private Node<T> node(int index) {
        if (index < (size >> 1)) {
            //下标小于长度的一半从头查询
            Node<T> node = first;
            for (int i = 0; i < index; i++)
                node = node.next;
            return node;
        } else {
            //下标大于长度的一半从尾查询
            Node<T> node = last;
            for (int i = size - 1; i > index; i--)
                node = node.prev;
            return node;
        }
    }

    //检查下标是否安全
    private void checkIndexSafe(int index) {
        if (index >= size || index < 0)
            throw new IndexOutOfBoundsException();
    }
    
    //节点内部类
    private class Node<T> {

        //上一个节点
        private Node<T> prev;

        //值
        private T value;

        //下一个节点
        private Node<T> next;

        //构造方法
        public Node(Node<T> prev, T value, Node<T> next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }

    }
    
    @Override
    public Iterator<T> iterator() {
        return new DoubleLinkedListIterator();
    }

    private class DoubleLinkedListIterator implements Iterator<T> {

        private Node<T> current;

        public DoubleLinkedListIterator() {
            current = first;
        }

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public T next() {
            T value = current.value;
            current = current.next;
            return value;
        }
    }
    
}
